package leetcode_100;

/**
 *@author 周杨
 *NextPermutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
		
	If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
		
	The replacement must be in-place, do not allocate extra memory.
		
	Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
 *describe:给定一个数组 在全排列中求下一个比他大的排列 如果没有 则反转数组
 *思路 : 尽可能的寻找最大公共前缀 采用自底向上方法  一直找逆序递减的数字 保证该数的后面数字是递增的  此处要替换  然后反转之后的数组
 *      时间复杂度 O(n^2)
 *2018年4月8日 下午3:36:48
 */
public class NextPermutation_31 {

	public static void main(String[] args) {
		//int nums[]=new int[] {3,2,1};
		int nums[]=new int[] {1,2,4,6,5,3};
		nextPermutation(nums);
		for(int i:nums)
			System.out.println(i);

	}
	
	public static void nextPermutation(int[] nums) {
		int temp;
        for(int i=nums.length-2;i>=0;--i) {
        	if(nums[i]<nums[i+1]) {
        		for(int j=nums.length-1;j>i;--j) {
        			if(nums[j]>nums[i]) {
        				temp=nums[i];
        				nums[i]=nums[j];
        				nums[j]=temp;
        				reverse(i+1, nums.length-1, nums);
        				return;
        			}
        		}
        	}
        }
        reverse(0, nums.length-1, nums);
    }
	
	public static void reverse(int i,int j,int nums[]) {
		int temp;
		while(i<j) {
			temp=nums[i];
			nums[i]=nums[j];
			nums[j]=temp;
			++i;
			--j;
		}
	}
	
}
